public class 正则表达式dp {
    public boolean isMatch(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int n = s.length;
        int m = p.length;
        boolean[][] dp = new boolean[n + 1][m + 1];// 0 没有访问过, 1 访问过为 true, 2 访问过为 false
        for (int j = m - 1; j >= 0; j--) {
            dp[n][j] = j + 1 < m && p[j + 1] == '*' && dp[n][j + 2];
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (j + 1 < m && p[j + 1] == '*') {
                    dp[i][j] = ((p[j] == '.' || s[i] == p[j]) && dp[i + 1][j]) || dp[i][j + 2];
                } else {
                    dp[i][j] = (p[j] == '.' || s[i] == p[j]) && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}
